from itertools import *
from functools import partial

def sumPos(a, b):
	return (int(a[0]+b[0]), int(a[1]+b[1]))
	
def subPos(a, b):
	return (int(a[0]-b[0]), int(a[1]-b[1]))

def multPos(c, pair):
	return (int(c*pair[0]), int(c*pair[1]))
	
def absPos(a):
	return (int(a[0]/abs(a[0])), int(a[1]/abs(a[1])))

class Game:
	boardWidth = 8
	boardHeight = 8
	def __init__(self):
		self.turn = 'O'
		self.validMoves = []
		self.createBoard()
		self.initializeBoard()
		
	def __getitem__(self, pos):
		return self.board[pos[0]*Game.boardHeight + pos[1]]
		
	def isEmpty(self, pos):
		return self.insideBoard(pos) and self[pos] == ' '
		
	def insideBoard(self, pos):
		return pos[0]>=0 and pos[1]>=0 \
			and pos[0] < Game.boardWidth \
			and pos[1] < Game.boardHeight
			
	def changeTurn(self, turn):
		return (turn=='O' and 'X') or 'O'
				
	def createBoard(self):		
		self.board = [' ' for i in range(Game.boardWidth*Game.boardHeight)]
				
	def initializeBoard(self):
		foo = lambda pos: (pos%Game.boardHeight<3 and ((int(pos/8)+(pos%8))%2 != 0) and 'O') or (pos%Game.boardHeight>=5 and ((int(pos/8)+(pos%8))%2 != 0) and 'X') or ' '
		self.board = map(foo, range(Game.boardWidth*Game.boardHeight))
		
	def move(self, org, dst):
		if self.insideBoard(org) and dst in self.validMoves:
			hasEaten = False
			dead = self.canEat(org, dst)
			if dead:
				f = lambda pos: (dead[0]*Game.boardHeight+dead[1]==pos and ' ') \
								or self.board[pos]
				self.board = map(f, range(Game.boardWidth*Game.boardHeight))

				hasEaten = True
				
			if (self.turn == 'X' and dst[1] == 0) or (self.turn == 'O' and dst[1] == Game.boardHeight-1):
				foo = lambda pos: (pos==org[0]*Game.boardHeight+org[1] and self.board[pos].lower()) \
							or self.board[pos]
				self.board = map(foo, range(Game.boardWidth*Game.boardHeight))
				
			foo = lambda pos: (pos==org[0]*Game.boardHeight+org[1] and ' ') \
						or (pos==dst[0]*Game.boardHeight+dst[1] and self.board[org[0]*Game.boardHeight+org[1]]) \
						or self.board[pos]
			self.board = map(foo, range(Game.boardWidth*Game.boardHeight))

			if (not hasEaten) or (not self.posHasMandatoryMoves(dst)):
				self.turn = self.changeTurn(self.turn)

		self.validMoves = []
		
	def canEat(self, org, dst):
		# TO DO: improve this...
		if self.isKing(org):
			diagonal = absPos(subPos(dst, org))
			mid = sumPos(org, diagonal)
			while self.isEmpty(mid) and mid != dst:
				mid = sumPos(mid, diagonal)
			if mid != dst and self.insideBoard(mid) and self[mid].upper() != self.turn:
				return mid
			else:
				return False
		else:
			mov = subPos(dst, org)
			if abs(mov[0])==1 or abs(mov[1])==1:
				return False
			mid = multPos(0.5, sumPos(org, dst))
			if (not self.isEmpty(mid)) and (self[mid].upper() != self.turn) and self.isEmpty(dst):
				return mid
			else:
				return False
		
	def isRetreating(self, pos, move):
		return (self.turn=='O' and pos[1]>move[1]) or (self.turn=='X' and pos[1]<move[1])
	
	def generateMoves(self, pos):
		if self.isKing(pos):
			self.generateKingMoves(pos)
		else:
			self.generateCommonMoves(pos)


	def generateEatingMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]
		
		canEatFromPos = partial(self.canEat, pos)
		futPos = lambda dir: sumPos(pos, multPos(2, dir))
		moves = [futPos(neighbor) for neighbor in neighborhood \
				if self.isEmpty(futPos(neighbor)) and canEatFromPos(futPos(neighbor))]
		
		return moves

	def hasMandatoryMoves(self):
		disjunction = lambda x, y: x or y
		positions = filter(lambda pos: self[pos].upper() == self.turn, product(range(Game.boardWidth), range(Game.boardHeight)))
		eatSomeone = [((self.isKing(pos) and len(self.generateKingEatingMoves(pos)) > 0) or (len(self.generateEatingMoves(pos)) > 0)) \
				for pos in positions]
		result = reduce(disjunction, eatSomeone)

		return result

	def posHasMandatoryMoves(self, pos):
		result = ((self.isKing(pos) and len(self.generateKingEatingMoves(pos)) > 0) or (len(self.generateEatingMoves(pos)) > 0))

		return result

	def isKing(self, pos):
		return self[pos] == 'o' or self[pos] == 'x'

	def generateCommonMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]

		self.validMoves = self.generateEatingMoves(pos)

		sumP = partial(sumPos, pos)
		self.validMoves += [sumP(neighbor) for neighbor in neighborhood \
						if self.isEmpty(sumP(neighbor)) and (not self.hasMandatoryMoves()) and (not self.isRetreating(pos, sumP(neighbor)))]


	def generateKingMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]

		self.validMoves = self.generateKingEatingMoves(pos)
		if not self.hasMandatoryMoves():
			self.validMoves += sum([self.longMoves(pos, neighbor) for neighbor in neighborhood], [])

	def generateKingEatingMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]
		moves = sum([self.foo(pos, neighbor) for neighbor in neighborhood], [])

		return moves
		
	def longMoves(self, pos, neighbor):
		dst = sumPos(pos, neighbor)
		if (not self.isEmpty(dst)):
			return []
		else:
			rec = self.longMoves(dst, neighbor)
			if rec:
				return [dst] + rec
			else:
				return [dst]	
		
	def foo(self, pos, neighbor):
		moves = []
		dst = sumPos(pos, neighbor)
		while self.isEmpty(dst):
			dst = sumPos(dst, neighbor)
			
		if self.insideBoard(dst) and self[dst].upper() != self.turn:
			moves = self.longMoves(dst, neighbor)
				
		return moves
				
